package sort;

import java.util.Random;

public class QuickSort {
    private final Random random = new Random();

    private void swap(int[] arr,int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private void choose_random_pivot(int[] arr, int left, int right){
        int randomIndex = this.random.nextInt(right-left+1) + left;
        swap(arr, left, randomIndex);
    }

    private int partition(int[] arr, int left, int right){
        choose_random_pivot(arr, left, right);
        int pivot = arr[left];
        int i = left;
        for(int j = left + 1; j<= right; j++){
            if(arr[j] <= pivot){
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i, left);
        return i;
    }

    public void quickSort(int[] arr, int left, int right){
        if(right > left){
            int pivotIndex = partition(arr, left, right);

            quickSort(arr, left, pivotIndex-1);
            quickSort(arr, pivotIndex + 1, right);
        }
    }

    public static void main(String[] args){
        QuickSort sort = new QuickSort();
        int[] arr = {5, 4, 3, 2, 1};
        sort.quickSort(arr, 0, arr.length-1);
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i] + " ");
        }
    }
}
